package com.leetcode.studyplan.algorithm.basis;

public class L_33_SearchInRotatedArray {

    public static void main(String[] args) {
        L_33_SearchInRotatedArray search =  new L_33_SearchInRotatedArray();
//        int[] nums = {4,5,6,7,0,1,2};
        int[] nums = {3,5,1};
//        int[] nums = {1};
        int target = 3;
        System.out.println(search.search(nums, target));
    }

    public int search(int[] nums, int target) {
       int res = -1;
       int left = 0;
       int right = nums.length - 1;
       while (left <= right) {
           int mid = (left + right) / 2;

           if (nums[mid] == target) {
               return mid;
           }

           if (nums[mid] < nums[right]) { // 右边有序
               if (target > nums[mid] && target <= nums[right]) { // 元素一定在右边
                   left = mid + 1;
               } else { // 其他两种情况都在左边
                   right = mid - 1;
               }
           } else { // 左边有序
               if (target < nums[mid] && target >= nums[left]) { // 一定在左边
                   right = mid - 1;
               } else { // 其他两个情况都在右边
                   left = mid + 1;
               }
           }

       }
       return res;
    }

    /**
     * 有序数组、二分查找
     * @param nums
     * @param target
     * @param start
     * @param end
     * @return
     */
    public int binarySearch(int[] nums, int target, int start, int end) {

        int res = -1;
        if (start <0 || end >= nums.length || start > end) {
            return res;
        }

        int mid = (start + end) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            return binarySearch(nums, target, start, mid - 1);
        }

        return binarySearch(nums, target, mid + 1, end);
    }

    /**
     * 逆转数组处理
     * @param nums
     * @param target
     * @param start
     * @param end
     * @return
     */
    public int binarySearchInOrder(int[] nums, int target, int start, int end) {

        int res = -1;
        if (start < 0 || end >= nums.length || start > end) {
            return res;
        }

        int mid = (start + end) / 2;
        if (nums[mid] == target) {
            return mid;
        }

        if (nums[mid] > nums[end]) { // 左边有序
            if (nums[mid] > target) { // 左边找
                return binarySearch(nums, target, start, mid - 1);
            } else {
                return binarySearchInOrder(nums, target, mid + 1, end);
            }
        } else if (nums[mid] < nums[end]) { // 右边有序
            if (nums[mid] > target) { // 左边找
                return binarySearchInOrder(nums, target, start, mid - 1);
            } else { // 右边找
                return binarySearch(nums, target, mid + 1, end);
            }
        }

        return res;

    }

}
